package Q337;

import java.util.*;

/**
 * 打家劫舍3
 * 二叉树
 */
public class Test {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode();
        TreeNode treeNode5 = new TreeNode(4);
        /*TreeNode treeNode6 = new TreeNode();
        TreeNode treeNode7 = new TreeNode(1);*/
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        /*treeNode3.left = treeNode6;
        treeNode3.right = treeNode7;*/
        System.out.println(new Solution().rob(treeNode));
    }
}

/**
 * 用层序遍历做的 ，自己测试没有问题，但是过不了，不知道问什么
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * 二叉树层序遍历
 */
class Solution {
    public int rob(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        int res1 = 0;
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode poll = queue.poll();
                if (count % 2 == 0) {
                    res += poll.val;
                } else {
                    res1 += poll.val;
                }
                if (poll.left != null) {
                    queue.add(poll.left);
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                }
            }
            count++;
        }

        return Math.max(res, res1);
    }
}

/**
 * 记忆递归
 * （普通递归要超时）
 */
class Solution2 {
    public int rob(TreeNode root) {
        Map<TreeNode, Integer> map = new HashMap<>();
        return helper(root, map);
    }

    private int helper(TreeNode root, Map<TreeNode, Integer> map) {
        if (root == null) {
            return 0;
        }
        if (map.containsKey(root)) {
            return map.get(root);
        }
        int value = root.val;
        if (root.left != null) {
            value += helper(root.left.left, map) + helper(root.left.right, map);
        }
        if (root.right != null) {
            value += helper(root.right.right, map) + helper(root.right.left, map);
        }
        int res = Math.max(value, helper(root.left, map) + helper(root.right, map));
        map.put(root,res);
        return res;
    }
}